Phylogenetic Combinatorics [draft]

Preface page ix
1 Preliminaries 1
1.1 Sets, set systems, and partially ordered sets 1
1.2 Graphs 4
1.3 Metric spaces 13
1.4 Computational complexity 19
2 Encoding X-trees 21
2.1 X-trees 21
2.2 Encoding X-trees with splits 23
2.3 Encoding X-trees with metrics 26
2.4 Encoding X-trees with quartets 27
3 Consistency of X-tree encodings 31
3.1 The 4-point condition 31
3.2 Compatibility 38
3.3 Quartet systems 42
4 From split systems to networks 50
4.1 The Buneman graph 51
4.2 The Buneman graph of a compatible split system 59
4.3 Median networks 63
4.4 Split networks 65
4.5 Split graphs and metrics: The theory of X-nets 72
5 From metrics to networks: The tight span 75
5.1 The tight span 75
5.2 A canonical contraction from P(D) onto T(D) 82
5.3 The tight span of a finite metric space 87
5.4 Networks from tight spans 93
5.5 Network realizations of metrics 97
5.6 Optimal and hereditarily optimal realizations 100
6 From quartet and tree systems to trees 104
6.1 On quartet systems 105
6.2 On set and tree systems 113
6.3 Constructing trees from quartet, tree, and set systems 118
6.4 Slim tree systems 121
6.5 Definitive set systems 128
7 From metrics to split systems and back 137
7.1 Buneman splits 137
7.2 Weakly compatible split systems 146
7.3 From weighted split systems to bivariate maps 161
7.4 The Buneman complex and the tight span 167
8 Maps to and from quartet systems 171
8.1 A Galois connection between split and quartet systems 171
8.2 A map from quartets to metrics 177
8.3 Transitive quartet systems 180
9 Rooted trees and the Farris transform 195
9.1 Rooted X-trees, clusters, and triplets 198
9.2 Dated rooted X-trees and hierarchical dissimilarities 202
9.3 Affine versus projective clustering and the
combinatorial Farris transform 205
9.4 Hierarchical dissimilarities, hyperbolic maps, and their
Farris transform 209
9.5 Hierarchical dissimilarities, generalized metrics,
and the tight-span construction 214
9.6 Algorithmic issues 218
10 On measuring and removing inconsistencies 222
10.1 k-compatibility 222
10.2 ?-hierarchical approximations 230
10.3 Quartet-Joining and QNet 236
Commonly used symbols 242
Bibliography 253
Index 261